Префиксно дрво
Уређена бинарна дрвета омогућавају ефикасну имплементацију структура са асоцијативним приступом код којих се приступ врши по кључу који није целобројна вредност већ стринг или нешто друго. Још једна структура у виду дрвета која омогућава ефикасан асоцијативан приступ је префиксно дрво такође познато под енглеским називом trie (од енглеске речи reTRIEval). Основна идеја ове структуре је да путање од корена до листова или до неких унутрашњих чворова кодирају кључеве, а да се подаци везани за тај кључ чувају у чвору док којег се долази проналажењем кључа дуж путање. У случају ниски, корен садржи празну реч, а преласком преко сваке гране се дна до тада формирану реч надовезује још један карактер. Притом, заједнички префиксни различитих кључева су представљени истим путањама од корена до тачке разликовања. Један пример оваквог дрвета, код којег су приказане ознаке придружене гранама, а не чворовима, је следећи:
a n d n t o a u a ć ž n h ž
Кључеви које дрво чува су ana, at, noć, nož, da, dan, duh и duž. Приметимо да се кључ da не завршава листом и да стога сваки чвор мора чувати информацију о томе да ли се њиме комплетира неки кључ (и у том случају садржати податак) или не. Илустрације ради, могу се приказати ознаке на чворовима, које представљају префиксе акумулиране до тих чворова. Треба имати у виду да овај приказ не илуструје имплементацију, већ само префиксе дуж гране. Симбол @ представља празну реч.
@ a n d an at no da du ana noć nož dan duh duž
У случају да неки чвор има само једног потомка и не представља крај неког кључа, грана до њега и грана од њега се могу спојити у једну, њихови карактери надовезати, а чвор елиминисати. Овако се добија компактнија репрезентација префиксног дрвета.
Поред општег асоцијативног приступа подацима, очигледна примена ове структуре је и имплементација коначних речника, на пример у сврхе аутоматског комплетирања или провере исправности речи које корисник куча на рачиунару или мобилном телефону.
Напоменимо још и да ова структура није резервисана за чување стрингова. На пример, у сличају целих бројева или бројева у покретном зарезу, кључ могу бити ниске битова које представљају такве бројеве.
У случају коначне азбуке величине \(m\), сложеност операција у најгорем случају је \(O(mn)\), где је \(n\) дужина речи која се тражи, умеће или брише, док је сложеност ових операција у просечном случају \(O(n)\). Када би се уместо префиксног дрвета користило балансирано уређено бинарно дрво, сложеност ових операција би у најгорем случају била \(O(M\log N)\), где је са \(N\) означен укупан број кључева који се чувају у дрвету, а са \(M\) максимална дужина кључа. Уколико су кључеви релативно кратки, предност префиксног дрвета је што сложеност зависи од дужине записа кључа, а не од броја елемената у дрвету. Мана је потреба за чувањем показивача уз сваки карактер у дрвету. Штавише, просторна сложеност префиксног дрвета је \(O(M\cdot m \cdot N)\), где је са \(N\) означен број кључева који се чувају у префиксном дрвету, а са \(M\) максимална дужина кључа.
Претрага и уметање се праволинијски имплементирају, док је у случају брисања некада потребно брисати више од једног чвора.